package dfs;

/**
 * @author wcj
 * @Date 2021/7/6 18:54
 * @Version 1.0
 */
public class CloseSeven {

    private static StringBuffer sb;
    private static int[] tmp;
    private static boolean[] target;
    private static int count;

    /**
     * 亲7数：能够被7整除的即为亲7数，对给出的一组个位数字中的数字进行随机组合，找出亲7数的个数
     * 深搜
     * ①递归方法的设计：dfs(int index)其中index表示当前访问到的数组中的数字下标
     * ②递归出口：index == arr.length()
     * ③递归组合方式：
     *
     * @param arr
     * @return
     */
    public static int closeSeven(int[] arr) {
        sb = new StringBuffer();
        tmp = arr;
        target = new boolean[arr.length];
        count = 0;
        dfs(0);
        return count;
    }

    public static void dfs(int index) {
        // 递归截止条件
        if (index == tmp.length && isClosedSeven(sb.toString())) {
            count++;
        }
        // 递归组合方式
        for (int i = 0; i < tmp.length; i++) {
            if (!target[i]) {
                target[i] = true;
                sb.append(tmp[i]);
                dfs(index + 1);
                sb.deleteCharAt(sb.length() - 1);
                target[i] = false;
            }
        }
    }

    public static boolean isClosedSeven(String s) {
        if (Integer.parseInt(s) % 7 == 0) {
            return true;
        }
        return false;
    }
}
